<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>冒泡排序</title>
</head>

<body>
    <script>
    // 解法 冒泡排序 
    // function bubbleSort(arr) {
    //     const len = arr.length
    //     if (len <= 1) return
    //     for (let i = 0; i < len - 1; i++) {
    //         // console.log(arr[i],'arr[i]');
    //         for (let j = 0; j < len - i - 1; j++) {
    //             // console.log(arr[j],'arr[j]');
    //             if (arr[j] > arr[j + 1]) {
    //                 const temp = arr[j]
    //                 arr[j] = arr[j + 1]
    //                 arr[j + 1] = temp
    //             }
    //         }
    //     }
    // }
    // 优化1 写法
    // function bubbleSort(arr) {
    //     const len = arr.length
    //     let stepCount = 0; // 步数计数器
    //     if (len <= 1) return
    //     for (let i = 0; i < len - 1; i++) {
    //         for (let j = 0; j < len - i - 1; j++) {
    //             stepCount++; // 每次比较都算一步
    //             if (arr[j] > arr[j + 1]) {
    //               [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
    //             }
    //         }
    //     }
    //     console.log(stepCount,'步数');
    //     return arr
    // }

    // 优化2 标志上一次移动的下标 有序标志 (isSorted)
    // function bubbleSort(arr) {
    //     const len = arr.length;
    //     let stepCount = 0; // 步数计数器
    //     if (len <= 1) return
    //     for (let i = 0; i < len - 1; i++) {
    //         let isSorted = true // 有序标志
    //         for (let j = 0; j < len - i - 1; j++) {
    //             stepCount++; // 每次比较都算一步
    //             if (arr[j] > arr[j + 1]) {
    //               [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
    //               isSorted = false
    //             }
    //         }
    //         if (isSorted) {
    //             console.log(isSorted, '交换结束===isSorted');
    //             break
    //         } // 如果没有发生交换，说明已经有序
    //     }
    //     console.log(stepCount,'步数');
    //     return arr
    // }


    // 优化3 标记上一轮已经有序的位置  无序边界 (sortBorder) 
    function bubbleSort(arr) {
        let stepCount = 0; // 步数计数器
        let compareCount = 0; // 比较次数计数器
        let swapCount = 0; // 交换次数计数器

        const len = arr.length;
        if (len <= 1) return arr;
        let sortBorder = len - 1; // 初始时无序边界为数组末尾
        let lastSwapIndex = 0; // 记录最后一次交换的位置
        for (let i = 0; i < len - 1; i++) {

            let isSorted = true; // 有序标志

            for (let j = 0; j < sortBorder; j++) {

                stepCount++; // 每次比较都算一步
                compareCount++; // 每次比较都计数

                if (arr[j] > arr[j + 1]) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                    isSorted = false; // 发生了交换，说明还不是完全有序
                    lastSwapIndex = j; // 记录最后一次交换的位置
                    swapCount++; // 每次交换都计数
                }
            }
            sortBorder = lastSwapIndex; // 更新无序边界，边界之后的元素已经有序
            if (isSorted) {
                console.log(isSorted, '交换结束isSorted');
                break; // 如果没有发生交换，说明已经有序
            }
        }

        console.log(stepCount, '步数');
        console.log('比较次数:', compareCount);
        console.log('交换次数:', swapCount);
        return arr;
    }

    // 功能测试
    const arr = [1, 4, 3, 6, 2, 5, 7, 9, 8]
    bubbleSort(arr)
    console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]
    </script>
</body>

</html>